:-dynamic distancia/3, melhor_sol/2.

/* Turista */
mod_turista(1,'FuturoSA',[c(igreja,1),c(palacio,4),c(museu,4),c(povoacao,5),c(pint_rup,3),c(antropologia,4),c(natureza,5),c(castelo,5),c(praca,3),c(artef,4),c(const_arq,4),c(escultura,4),c(pintura,1),c(tapecarias,1),c(literatura,1),c(jardim,4)]).

tmp_disp_tur(1,3610).

/* Poi */
poi(16,'PalÃ¡cio de Cristal',jardim,4).
poi(17,'Quinta de Santo InÃ¡cio',natureza,3).
poi(18,'Parque BiolÃ³gico de Gaia',natureza,4).
poi(19,'Jardim Soares dos Reis',jardim,2).
poi(20,'Jardim de S. LÃ¡zaro',jardim,3).
poi(21,'RuÃ­nas de Conimbriga',povoacao,5).
poi(22,'O Menino do Lapedo',antropologia,4).
poi(23,'Pinturas de Foz CÃŽa',antropologia,4).
poi(24,'CitÃ¢nia de Sanfins',povoacao,5).
poi(25,'Cromeleque dos Almendres',antropologia,3).
poi(26,'Anta do Barrocal',antropologia,2).
poi(27,'Castelo de Almourol',castelo,3).
poi(28,'Castelo de Santa Maria da Feira',castelo,3).


/* Duracao */
duracao(16,120).
duracao(17,150).
duracao(18,135).
duracao(19,135).
duracao(20,120).
duracao(21,80).
duracao(22,55).
duracao(23,60).
duracao(24,105).
duracao(25,30).
duracao(26,30).
duracao(27,60).
duracao(28,60).


/* Horario */
horario(19,0,23).
horario(20,0,23).
horario(21,8,12).
horario(22,8,12).
horario(23,8,12).
horario(24,8,12).
horario(25,8,21).
horario(26,8,12).
horario(27,8,13).
horario(28,8,13).


/* Coordenadas */
coord_poi(16,-13,0).
coord_poi(17,-9,16).
coord_poi(18,-8,-8).
coord_poi(19,-6,12).
coord_poi(20,14,0).
coord_poi(21,-4,-7).
coord_poi(22,0,-13).
coord_poi(23,1,4).
coord_poi(24,4,-10).
coord_poi(25,4,0).
coord_poi(26,7,-3).
coord_poi(27,10,-10).
coord_poi(28,15,-13).
coord_poi(96,-16,16).
coord_poi(97,-10,16).
coord_poi(98,-4,16).
coord_poi(99,-10,14).
coord_poi(100,-8,12).
coord_poi(101,-4,12).
coord_poi(102,1,10).
coord_poi(103,-16,10).
coord_poi(104,-10,10).
coord_poi(105,-3,7).
coord_poi(106,-2,4).
coord_poi(107,0,4).
coord_poi(108,2,4).
coord_poi(109,-16,0).
coord_poi(110,-11,0).
coord_poi(111,-3,0).
coord_poi(112,0,0).
coord_poi(113,1,0).
coord_poi(114,9,0).
coord_poi(115,15,0).
coord_poi(116,5,-3).
coord_poi(117,9,-3).
coord_poi(118,12,-3).
coord_poi(119,-4,-6).
coord_poi(120,9,-6).
coord_poi(121,16,-6).
coord_poi(122,-7,-7).
coord_poi(123,-14,-8).
coord_poi(125,-3,-9).
coord_poi(126,-2,-9).
coord_poi(127,-1,-8).
coord_poi(128,6,-8).
coord_poi(129,-16,-10).
coord_poi(130,-10,-11).
coord_poi(131,-5,-12).
coord_poi(132,-3,-10).
coord_poi(133,-3,-12).
coord_poi(134,6,-10).
coord_poi(135,16,-11).
coord_poi(136,-16,-16).
coord_poi(137,-13,-16).
coord_poi(138,-10,-16).
coord_poi(139,-2,-16).
coord_poi(140,6,-14).
coord_poi(141,6,-16).
coord_poi(142,16,-16).

/* Coordenadas iniciais e finais */
coord_poi(-1,-13,0).
coord_poi(-2,15,-13).


/* Seccoes */
seccao(109,16,0).
seccao(103,97,0).
seccao(117,118,0).
seccao(116,26,0).
seccao(108,116,0).
seccao(107,23,0).
seccao(106,107,0).
seccao(105,106,0).
seccao(101,105,0).
seccao(100,19,0).
seccao(99,100,0).
seccao(97,17,0).
seccao(96,97,0).
seccao(107,112,0).
seccao(102,107,0).
seccao(105,102,0).
seccao(110,105,0).
seccao(112,113,0).
seccao(111,112,0).
seccao(110,111,0).
seccao(112,127,0).
seccao(127,126,0).
seccao(126,132,0).
seccao(132,131,0).
seccao(131,138,0).
seccao(114,20,0).
seccao(122,21,0).
seccao(119,125,0).
seccao(125,132,0).
seccao(132,133,0).
seccao(133,139,0).
seccao(123,18,0).
seccao(18,125,0).
seccao(125,126,0).
seccao(126,24,0).
seccao(134,27,0).
seccao(129,130,0).
seccao(130,131,0).
seccao(131,133,0).
seccao(133,22,0).
seccao(140,142,0).
seccao(136,129,0).
seccao(129,109,0).
seccao(109,103,0).
seccao(103,96,0).
seccao(137,130,0).
seccao(130,18,0).
seccao(18,111,0).
seccao(104,99,0).
seccao(99,97,0).
seccao(141,140,0).
seccao(140,134,0).
seccao(134,128,0).
seccao(120,117,0).
seccao(117,114,0).
seccao(142,135,0).
seccao(135,121,0).
seccao(17,98,0).
seccao(19,101,0).
seccao(23,108,0).
seccao(26,117,0).
seccao(16,110,0).
seccao(20,115,0).
seccao(21,125,0).
seccao(24,134,0).
seccao(27,28,0).
seccao(28,135,0).
seccao(22,140,0).
seccao(-1,110,0).
seccao(-2,135,0).
seccao(109,-1,0).
seccao(27,-2,0).


/* Listar poi para turista */
lista_poi_turista(IDtur,L):- lista_f_turista(IDtur,LFtur), passar(LFtur,L).

lista_f_turista(IDtur,LFtur):- setof(f(F,IDpoi),avalia_poi_t(IDpoi,IDtur,F),L),reverse(L,LFtur).

avalia_poi_t(IDpoi,IDtur,F):- poi(IDpoi,_,Tipo,Cpoi),mod_turista(IDtur,_,L),member(c(Tipo,Nt),L),f_aval(Cpoi,Nt,F).

f_aval(Cpoi,Nt,F):-F is Cpoi + Nt.


passar([],[]):-!.
passar([f(_,X)|L],[X|L1]):-passar(L,L1).



/* Calcular distancias entre poi */
todas_distancias:-findall(_,(calc_distancia(P1,P2,D),assertz(distancia(P1,P2,D))),_).

calc_distancia(P1,P2,D):-
	coord_poi(P1,X1,Y1),
	coord_poi(P2,X2,Y2),
	P2>P1,
	DX is X1-X2,
	DY is Y1-Y2,
	D is sqrt(DX*DX+DY*DY).

:-todas_distancias.




/* tds_dist_sec:- findall(_,(atrib_dist(P1,P2,D), assertz(seccao(P1,P2,D))),_), findall(_,(retract(seccao(_,_,0))),_).

atrib_dist(P1,P2,D):- (distancia(P1,P2,D); distancia(P2,P1,D)), seccao(P1,P2,_).

:-tds_dist_sec. */


/* Melhor caminho */
melhor_caminho(Lpoi,Lpoim,D):-findall(Lpoip12,(permuta(Lpoi,Lpoip),append([-1|Lpoip],[-2],Lpoip12)),LLpoi),menor_caminho(LLpoi,Lpoim,D),write(Lpoim),write(' '), write(D).
 
menor_caminho([Lpoi],Lpoi,D):-!,calc_dist_total(Lpoi,D).
menor_caminho([Lpoi|LLpoi],Lpoim,D):-menor_caminho(LLpoi,Lpoim2,D2),calc_dist_total(Lpoi,D1),((D1<D2,!,Lpoim=Lpoi,D is D1);(Lpoim=Lpoim2,D is D2)).

calc_dist_total([_],0).
calc_dist_total([P1,P2|LP],D):-calc_dist_total([P2|LP],D2LP),((distancia(P1,P2,D12),!);distancia(P2,P1,D12)),D is D12+D2LP.

permuta([ ],[ ]).
permuta(L,[X|L1]):-elimina_(X,L,Li),permuta(Li,L1).

elimina_(X,[X|L],L).
elimina_(X,[Y|L],[Y|L1]):-elimina_(X,L,L1).
 


/* Caminho caixeiro viajante */
caminho_caixeiro_viajante(Lpoi,[-1|Lpoicv],D):-menor_distancia_membro_lista(-1,Lpoi,P,Lpoi1,D1),
							caminho_caixeiro_viajante1(P,Lpoi1,Lpoicv,Pf,Dpoi),
							(distancia(Pf,-2,D2);distancia(-2,Pf,D2)),
							D is D1+Dpoi+D2.


caminho_caixeiro_viajante1(P,[],[P,-2],P,0):-!.
caminho_caixeiro_viajante1(P,L,[P|Lcv],Pf,D):-menor_distancia_membro_lista(P,L,P1,L1,D1),caminho_caixeiro_viajante1(P1,L1,Lcv,Pf,D2),D is D1+D2.


menor_distancia_membro_lista(X,L,Ym,L1m,Dm):-findall(p(Y,L1,D),distancia_membro_lista(X,L,Y,L1,D),LYLD),menor_dml(LYLD,Ym,L1m,Dm).

distancia_membro_lista(X,L,Y,L1,D):-remove(Y,L,L1),((distancia(X,Y,D));distancia(Y,X,D)).

menor_dml([p(Y,L,D)],Y,L,D).
menor_dml([p(Y1,L1,D1)|LYLD],Ym,Lm,Dm):-menor_dml(LYLD,Y2,L2,D2),((D1<D2,!,Lm=L1,Ym=Y1,Dm is D1);(Lm=L2,Ym=Y2,Dm is D2)).



remove(X,[X|L],L).

remove(X,[Y|L],[Y|L1]):-
  remove(X,L,L1).


/*apaga(_,[ ],[ ]).
apaga(X,[X|L],M):-!,apaga(X,L,M).
apaga(X,[Y|L],[Y|M]):-apaga(X,L,M).*/

/* Selecionar um tourista */
selecciona_tour(IDtur,Lm,Ttotal):-tmp_disp_tur(IDtur,TT),roteiro_tmp_disp(IDtur,Tpoi,R),
					subconjunto(R,R1,Tpoi,Tpoi1),caminho_caixeiro_viajante(R1,Lm,D),Tcaminho is D*factor(Idfac), 
					Ttotal is Tpoi1+Tcaminho,Ttotal=<TT,!.

subconjunto([],[],T,T).
subconjunto([X|L],[X|L1],T,Tf):-subconjunto(L,L1,T,Tf).
subconjunto([Y|L],L1,T,Tf):-duracao(Y,TY), T1 is T-TY,subconjunto(L,L1,T1,Tf).
						
roteiro_tmp_disp(IDtur,T,R):-lista_poi_turista(IDtur,L),tmp_disp_tur(IDtur,X), poi_visitar(L,X,R,0,T).

poi_visitar([], _, [], ST, ST):-!.
poi_visitar([IDpoi|_], T, [], ST, ST):-duracao(IDpoi, TPoi), T<TPoi, !.
poi_visitar([IDpoi|LPoi], T, [IDpoi|LPoi1], STa, STf):-duracao(IDpoi, TPoi),T1 is T-TPoi, ST1 is STa+TPoi, poi_visitar(LPoi, T1, LPoi1, ST1, STf). 



/* Execucao */
executa(IDtur):- selecciona_tour(IDtur,Lm,Ttotal), write(Lm), nl, traj_entre_poi(Lm).


traj_entre_poi([H|[]]):- !.
traj_entre_poi([H,HS|T]):- hbf(H,HS,Perc,Total),
	nl, write(Perc), nl, append([HS],T,Poi_rest), 
	traj_entre_poi(Poi_rest).


/* A star */
hbf(Orig,Dest,Perc,Total):-
	estimativa(Orig,Dest,H),
	hbf1([c(H/0,[Orig])],Dest,P,Total),
	reverse(P,Perc).
							
hbf1(Percursos,Dest,Percurso,Total):-
	menor_percursoh(Percursos,Menor,Restantes),
	percursos_seguintesh(Menor,Dest,Restantes,Percurso,Total).
										
percursos_seguintesh(c(_/Dist,Percurso),Dest,_,Percurso,Dist):-
	Percurso=[Dest|_].

percursos_seguintesh(c(_,[Dest|_]),Dest,Restantes,Percurso,Total):-
	!, hbf1(Restantes,Dest,Percurso,Total).

percursos_seguintesh(c(_/Dist,[Ult|T]),Dest,Percursos,Percurso,Total):-
	findall(c(H1/D1,[Z,Ult|T]),proximo_noh(Ult,T,Z,Dist,Dest,H1/D1),Lista),
	append(Lista,Percursos,NovosPercursos),
	hbf1(NovosPercursos,Dest,Percurso,Total).
																		
menor_percursoh([Percurso|Percursos],Menor,[Percurso|Resto]):-
	menor_percursoh(Percursos,Menor,Resto),menorh(Menor,Percurso),!.

menor_percursoh([Percurso|Resto],Percurso,Resto).

menorh(c(H1/D1,_),c(H2/D2,_)):-C1 is H1+D1, C2 is H2+D2, C1<C2.

proximo_noh(X,T,Y,Dist,Dest,H/Dist1):-
	(seccao(X,Y,Z);seccao(Y,X,Z)),
	\+ member(Y,T),
	Dist1 is Dist + Z,
	estimativa(Y,Dest,H).

estimativa(C1,C2,Est):-
	coord_poi(C1,X1,Y1),
	coord_poi(C2,X2,Y2),
	DX is X1-X2,
	DY is Y1-Y2,
	Est is sqrt(DX*DX+DY*DY).

